#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <unordered_set>
using namespace std;
class Solution
{
public:
    vector<string> findWords(vector<string> &words)
    {
        vector<string> rows = {"qwertyuiop", "asdfghjkl", "zxcvbnm"};
        vector<string> ans = {};
        for (int i = 0; i < words.size(); i++)
        {
            int k = 0, row = 0;
            do
            {
                // get row line
                char w0 = (words[i][0] >= 'A' && words[i][0] <= 'Z') ? (words[i][0] + 32) : words[i][0];
                if (rows[k].find_first_of(w0) != string::npos)
                {
                    row = k;
                    break;
                }
                k++;

            } while (k < 3);

            // search i+1 char
            int j = 1, wjLen = words[i].length();
            while (j < wjLen)
            {
                char wj = (words[i][j] >= 'A' && words[i][j] <= 'Z') ? (words[i][j] + 32) : words[i][j];
                if (rows[row].find_first_of(wj) == string::npos)
                {
                    break;
                }
                j++;
            }
            if (j == wjLen)
            {
                ans.push_back(words[i]);
            }
        }
        return ans;
    }

    vector<string> findWords_2(vector<string> &words)
    {
        unordered_map<char, int> mp;
        vector<string> keyboard = {"qwertyuiopQWERTYUIOP", "asdfghjklASDFGHJKL", "zxcvbnmZXCVBNM"};
        for (int i = 0; i < keyboard.size(); i++)
        {
            for (char c : keyboard[i])
            {
                mp[c] = i + 1;
            }
        }

        vector<string> result;
        for (int i = 0; i < words.size(); i++)
        {
            int j = 0, wordsLen = words[i].size();
            string word = words[i];
            for (; j < wordsLen - 1; j++)
            {
                if (mp[word[j]] != mp[word[j + 1]])
                {
                    break;
                }
            }
            if (j == wordsLen - 1)
            {
                result.push_back(words[i]);
            }
        }
        return result;
    }

    vector<string> findWords_3(vector<string> &words)
    {
        unordered_set<char> myset1 = {'q', 'w', 'e', 'r', 't', 'y', 'u', 'i', 'o', 'p'};
        unordered_set<char> myset2 = {'a', 's', 'd', 'f', 'g', 'h', 'j', 'k', 'l'};
        unordered_set<char> myset3 = {'z', 'x', 'c', 'v', 'b', 'n', 'm'};
        vector<string> ans;
        for (auto &w : words)
        {
            int n = w.size();
            int k = 2;
            char c = w[0];
            if (c >= 'A' && c <= 'Z')
                c = c - 'A' + 'a';
            if (myset1.count(c))
                k = 0;
            else if (myset2.count(c))
                k = 1;
            bool pos = true;
            for (int i = 1; i < n; i++)
            {
                char c1 = w[i];
                if (c1 >= 'A' && c1 <= 'Z')
                    c1 = c1 - 'A' + 'a';
                if (k == 0 && myset1.count(c1) == 0)
                {
                    pos = false;
                    break;
                }
                else if (k == 1 && myset2.count(c1) == 0)
                {
                    pos = false;
                    break;
                }
                else if (k == 2 && myset3.count(c1) == 0)
                {
                    pos = false;
                    break;
                }
            }
            if (pos)
                ans.push_back(w);
        }
        return ans;
    }
};
int main()
{
    Solution s;
    vector<string> words = {"Hello", "Alaska", "Dad", "Peace"};
    vector<string> ans = s.findWords_2(words);
    for (string a : ans)
    {
        cout << a << " ";
    }
    cout << endl;
    return 0;
}
